#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read<int>()
#define lin read<ll>()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

template <typename T>
T read(){
	T x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int N = 65;
const int mod = 1e9+7;

ll f[N][2][2][2][2],n,m;
int k,nb[N],mb[N],ctn,ctm;
bool g[N][2][2][2][2];

ll dfs(int cur,bool able,bool dif,bool dn,bool dm){
	if(cur == 0) return able;
	if(g[cur][able][dif][dn][dm]) return f[cur][able][dif][dn][dm];
	ll tot = 0;
	int upn = dn ? k - 1 : nb[cur],upm = dm ? k - 1 : mb[cur];
	for(int i = 0;i <= upn;i++)
		for(int j = 0;(j <= i || dif) && j <= upm;j++){
			tot += dfs(cur - 1,able | (i < j),dif | (j != i),dn | (i < upn),dm | (j < upm));
			tot %= mod;
		}
	g[cur][able][dif][dn][dm] = 1; return f[cur][able][dif][dn][dm] = tot;
}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	int t = in; k = in;
	while(t--){
		n = lin,m = lin; ctn = ctm = 0;
		memset(nb,0,sizeof(nb)); memset(mb,0,sizeof(mb));
		while(n > 0) nb[++ctn] = n % k,n /= k;
		while(m > 0) mb[++ctm] = m % k,m /= k;
		memset(g,0,sizeof(g));
		ll ans = dfs(max(ctn,ctm),0,0,0,0);
		printf("%lld\n",ans);
	}
	return 0;
}

